package sort.test4_11;

import java.util.Arrays;

public class RadixSort {

    public  int[]  radixSort(int[]  nums){
        if (nums.length==0){
            return null;
        }
        int length = nums.length;
        int max=Integer.MIN_VALUE;
        for (int i = 0; i <length ; i++) {
            max=Math.max(nums[i],max );
        }

        for (int exp = 1; max/exp>0 ; exp*=10) {
            sort(nums,exp);
        }
        return nums;
    }

    public  void  sort(int[] nums,int exp){
        int length = nums.length;
        int[] output=new int[length];
        int[] countArray=new int[10];
        for (int i = 0; i <length; i++) {
            countArray[(nums[i]/exp)%10]++;
        }
        for (int i = 1; i <10; i++) {
            countArray[i]+=countArray[i-1];
        }

//        for (int i = 0; i < length; i++) {
//            output[--countArray[(nums[i]/exp)%10]]=nums[i];
//        }

        //  CKG TODO 2023/4/11:  明白这个地方为什么需要倒着了 因为经过上一轮的排序 相同位数的数值已经是有顺序的了 比如 3,5   在下一轮的技术中 都分在0桶中
        //  CKG TODO 2023/4/11: 这时候倒着排序 刚好可以将5排在3的后面
        for (int i = nums.length-1; i>=0  ; i--) {
//  CKG TODO 2023/4/11:  此处必须使用output来接收排完序列后的数组  否则自己修改着自己一边又遍历这自己 乱套了
            output[--countArray[(nums[i]/exp)%10]]=nums[i];
//            countArray[(nums[i]/exp)%10]--;
        }


        for (int i = 0; i < length; i++) {
            nums[i]=output[i];
        }
        output=null;
        countArray=null;
    }

    public static void main(String[] args) {
        RadixSort radixSort = new RadixSort();
        int arr[] ={3,44,38,5,47};
        radixSort.radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
